package cn.suchan.jianzhi.q37_sortarray;

/**
 * 知识点：数字在排序数组中出现的次数
 * 题目描述
 * 统计一个数字在排序数组中出现的次数。
 *
 * @author suchan
 * @date 2019/06/03
 */
public class Solution {

    private int count = 0;

    /**
     * 直接遍历数组进行统计
     *
     * @param array
     * @param k
     * @return
     */
    public int GetNumberOfK(int[] array, int k) {
        if (array.length <= 0 || array == null) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == k) {
                count++;
            }
        }
        return count;
    }

    /**
     * 因为是排好序的数组，所以重复的数字肯定是集中在一起的，
     * 从左边开始遍历，获取重复数字的左边第一个位置下标；
     * 再从右边开始遍历，获取重复数字的右边第一个位置下标。
     * 将左右第一个位置下标进行计算可获得数字的重复次数
     *
     * @param array
     * @param k
     * @return
     */
    public int GetNumberOfK1(int[] array, int k) {
        if (array.length <= 0 || array == null) {
            return 0;
        }

        int left = -1;
        int right = -1;

        for (int i = 0; i < array.length; i++) {
            if (array[i] == k) {
                left = i;
                break;
            }
        }
        for (int i = array.length - 1; i >= 0; i--) {
            if (array[i] == k) {
                right = i;
                break;
            }
        }
        int result = 0;
        if (left >= 0 && right >= 0) {
            result = right - left + 1;
        }
        return result;
    }

    /**
     * 用二分法进行遍历计数，
     * 如果中间的数等于目标数，那就往左右两边查找是否还有相等的；
     * 如果中间的数小于目标数，则往右边继续查找；
     * 如果中间的数大于目标数，则往左边继续查找。
     *
     * @param array
     * @param k
     * @return
     */
    public int GetNumberOfK2(int[] array, int k) {
        if (array.length <= 0 || array == null) {
            return 0;
        }
        int count = dichotomy(array, 0, array.length - 1, k);
        return count;
    }

    private int dichotomy(int[] array, int start, int end, int k) {
        int mid = (end + start) / 2;

        if (mid >= start && mid <= end) {
            if (array[mid] == k) {
                count++;
                dichotomy(array, start, mid - 1, k);
                dichotomy(array, mid + 1, end, k);
            } else if (array[mid] < k) {
                dichotomy(array, mid + 1, end, k);
            } else if (array[mid] > k) {
                dichotomy(array, start, mid - 1, k);
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {0, 0, 0, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6, 6, 6, 6};
        int result = solution.GetNumberOfK2(arr, 3);
        System.out.println(result);
    }
}
